package oj;
import java.util.*;

//从前序和中序遍历序列构造二叉树：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
//求解问题时，尽量多用 list 少用数组
public class Solution_105 {
    //方法一：用 list 解决问题
    public static List<Integer> toList(int[] array){
        List<Integer> list = new ArrayList<>();
        for(int e : array){
            list.add(e);
        }
        return list;
    }
    //构建树的方法
    public static TreeNode build(List<Integer> preorder, List<Integer> inorder){
        if(preorder.size() == 0){
            //说明前序遍历没有元素，是空树
            return null;
        }
        //1.先确定根的值
        int rootVal = preorder.get(0);  //size > 0
        //2.确定 rootVal 在中序遍历中的下标，也就是左子树的结点个数
        int leftSize = inorder.indexOf(rootVal);
        int rightSize = inorder.size() - leftSize - 1;  //其实也可以不用进行计算，不会用到
        //3.先创建根结点
        TreeNode root = new TreeNode((char) rootVal);
        //4.切出左子树的前序遍历和中序遍历
        List<Integer> leftPreorder = preorder.subList(1,1 + leftSize);
        List<Integer> leftInorder = inorder.subList(0,leftSize);
        //使用相同的方法对左子树的前中序遍历构建二叉树
        TreeNode left = build(leftPreorder,leftInorder);
        //5.切除右子树的前序遍历和中序遍历
        List<Integer> rightPreorder = preorder.subList(leftSize + 1,preorder.size());
        List<Integer> rightInorder = inorder.subList(leftSize + 1,inorder.size());
        TreeNode right = build(rightPreorder,rightInorder);
        //6.把左右子树和根结点组装在一起
        root.left = left;
        root.right = right;
        //7.返回组装好的树
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //将数组转换为 list
        List<Integer> preorderList = toList(preorder);
        List<Integer> inorderList = toList(inorder);

        return build(preorderList,inorderList);
     }
     //方法二：利用数组进行求解(用数组求解要求我们对下标的控制要很严谨)
//    public static TreeNode build(int[] preorder,int pfrom,int pto,int[] inorder,int ifrom,int ito){
//        //size = pto - pfrom
//        //断言 pto - pfrom = ito - iform
//        int size = pto - pfrom;
//        if(size == 0){
//            return null;
//        }

//        //1.根的值时前序区间中的第一个元素(不是数组的第一个元素)
//        int rootVal = preorder[pfrom];
//        TreeNode root = new TreeNode(rootVal);

//        //2.在中序区间中找到 rootVal 的下标
//        int index = -1;
//        for(int i = ifrom;i < ito;i++){
//            if(inorder[i] == rootVal){
//                index = i;
//            }
//        }
//        //i != -1。因为根的值一定在中序序列的区间中
//        //这个时候的左子树结点个数 leftSize != index
//        int leftSize = index - ifrom;

//        //3.切除左子树的前/中序序列区间，找到其开始下标和结束下标
//        //前序的开始和结束
//        int leftPfrom = pfrom + 1;
//        int leftPto = pfrom + 1 + leftSize;
//        //中序的开始和结束
//        int leftIfrom = ifrom;
//        int leftIto = ifrom + leftSize;
//        //构建左子树
//        root.left = build(preorder, leftPfrom, leftPto, inorder, leftIfrom, leftIto);

//        4.切除右子树的前/中序序列区间
//        //前序
//        int rightPfrom = pfrom + 1 + leftSize;
//        int rightPto = pto;
//        //中序
//        int rightIfrom = ifrom + leftSize + 1;
//        int rightIto = ito;
//        //构建右子树
//        root.right = build(preorder, rightPfrom, rightPto, inorder, rightIfrom, rightIto);
//        //返回根结点
//        return root;
//
//    }
//    public TreeNode buildTree(int[] preorder,int[] inorder){
//        //利用 int[] array + int fromIndex + int toIndex
//        //数组，包含开始下标，不包含结束下边，左闭右开
//        return build(preorder,0,preorder.length,inorder,0,inorder.length);
//    }
}
